package com.vinjune.algorithm.algorithms;


/**
*@author 作者：zhangwenjun
*@version 创建时间：2015年12月9日 下午5:15:25
*最短路径
*/

public class Dijkstra {
	private static int MAX = Integer.MAX_VALUE;
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int n = 7;
		int v = 0;
		int[][] cost = new int[][]{{0,20,50,30,MAX,MAX,MAX},
							      {MAX,0,25,MAX,MAX,70,MAX},
							      {MAX,MAX,0,40,25,50,MAX},
							      {MAX,MAX,MAX,0,55,MAX,MAX},
							      {MAX,MAX,MAX,MAX,0,10,70},
							      {MAX,MAX,MAX,MAX,MAX,0,50},
							      {MAX,MAX,MAX,MAX,MAX,MAX,0}};
		
		dijkstra(n, v, cost);
	}

	/**
	 * 迪杰斯特拉
	 * @param n 结点个数
	 * @param v 开始的节点
	 * @param cost 代价邻接矩阵
	 */
	public static void dijkstra(int n, int v, int[][] cost) {
		int[] dist = new int[n]; //记录最小距离
		int[] s = new int[n]; //记录是否被访问，-1表示未访问，其他表示访问次序
		int p = 0; //记录访问顺序，每次+1
		for(int k=0;k<n;k++) {  //初始化
			dist[k] = cost[v][k];
			s[k] = -1;
		}
		//访问v节点（开始的节点）
		s[v] = 0;
		dist[v] = 0;
		
		for(int m=0;m<n-1;m++) {
			int u = min(dist, s); //找到距离最小的一个顶点（该顶点未被访问过）
			p++; //访问循序+1
			s[u] = p; //将u加入到s中
			for(int i=0;i<n;i++) {  //调整dist中的距离
				if(s[i] == -1) { //节点i未被访问
					if(dist[u]!=MAX && cost[u][i]!=MAX) {
						if(dist[u]+cost[u][i] < dist[i])
							dist[i] = dist[u]+cost[u][i];
					}
				}
			}
		}
		
		for(int j=0;j<n;j++)
			System.out.print(dist[j] + " ");
	}
	
	/**
	 * 求最小值
	 * @param dist
	 * @param s
	 * @return
	 */
	private static int min(int[] dist, int[] s) {
		int min = 0;
		for (int i = 0; i < dist.length; i++) {
			while (s[min] != -1)
				// 首先找到未被访问节点序列的第一个节点
				min++;
			if (s[i] == -1) { // 该节点未被访问
				if (dist[i] < dist[min])
					min = i;
			}
		}
		return min;
	}

}


